/*
题目: 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

https://leetcode.cn/problems/majority-element
 */
public class MajorityElement {
    public int majorityElement(int[] nums) {
        return divide(nums, 0, nums.length);
    }

    private int divide(int[] nums, int start, int end) {
        // 如果只有一个元素
        if (start == end - 1)
            return nums[start];

        int mid = start + ((end - start) >> 1);
        int left = divide(nums, start, mid);
        int right = divide(nums, mid, end);

        // 如果左区间 和 右区间返回的元素相等
        if (left == right)
            return left;

        int leftCount = getCount(nums, start, mid + 1, left);
        int rightCount = getCount(nums, mid + 1, end, right);

        return leftCount > rightCount ? left : right;
    }

    private int getCount(int[] nums, int start, int end, int target) {
        int count = 0;
        for (int i = start; i < end; i++) {
            if (nums[i] == target)
                count ++;
        }
        return count;
    }
}
